#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll inf=1e13;
int T,a,b,val[10];
vector<pair<int,ll> >e[10];
inline int minp(int x){
	for(int i=2;1ll*i*i<=x;i++){
		if(!(x%i)) return i;
	}
	return x;
}
int Gcd(int x,int y){
	return !y?x:Gcd(y,x%y);
}
ll Lcm(int x,int y){
	return 1ll*x*y/Gcd(x,y);
}
bool vis[10];
ll ans=inf;
void dfs(int u,ll len){
	vis[u]=1;
	if(u==2) ans=min(ans,len);
	for(auto i:e[u]){
		int v=i.first;
		ll w=i.second;
		if(!vis[v]) dfs(v,len+w);
	}
	vis[u]=0;
}

int main(){
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		ans=inf;
		scanf("%d%d",&a,&b);
		if(Gcd(a,b)==min(a,b)){
			printf("%d\n",max(a,b));
			continue;
		}
		if(Gcd(a,b)>1){
			printf("%d\n",a+b);
			continue;
		}
		val[1]=a,val[2]=b,val[3]=minp(a),val[4]=minp(b),val[5]=2;
		for(int i=1;i<=5;i++) e[i].resize(0),vis[i]=0;
		for(int i=1;i<=5;i++)
			for(int j=1;j<=5;j++){
				e[i].emplace_back(j,Lcm(val[i],val[j]));
			}		
		dfs(1,0);
		printf("%lld\n",ans);
	}
	return 0;
} 
/*
3
3 4
10 15
2 4

10
303 401
303 402
303 403
303 404
303 405
303 406
303 407
303 408
303 409
303 410

*/
